package Intermediate_algorithm.Linklist;

/*
奇偶链表
给定单链表的头节点head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出:[1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

提示:
n ==  链表中的节点数
0 <= n <= 104
-10^6 <= Node.val <= 10^6
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/linked-list/fe0kj/
 */
public class _02奇偶链表 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //分离节点后合并
    //双指针，每个指针代表一个链表
    //O(n)
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        ListNode temp = second;
        while (second != null && second.next != null) {
            first.next = second.next;
            first = first.next;
            second.next = first.next;
            second = second.next;
        }
        first.next = temp;
        return head;
    }
}
